#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define false 0
#define true 1
#define max 100
typedef struct {
	int value;    //value为具体数值 
	int row,col;  //row为行,col为列 
}Array;
typedef struct {
	Array data[max+1];    
	int rows,cols,nums;   //nums为非零元素个数 
}Arrays;
//创建稀疏矩阵 
int InitArray(Arrays *L,int rows,int cols,int nums){
	int i,j;
	L->nums=nums;
	L->cols=cols;
	L->rows=rows;
	assert(L->nums<max);
	printf("-------------\n");
	printf("请依次输入非零元素的行数,列数,值:\n");
	for (int i = 1; i <= L->nums; i++) {
		scanf("%d %d %d", &L->data[i].row, &L->data[i].col, &L->data[i].value);
		}
		printf("创建成功！\n");
		return true;
	}
//遍历输出稀疏矩阵  三元组形式
void bianli1(Arrays *L) {
	printf("-------------三元组形式形式遍历输出:\n");
	for (int i = 1; i <= L->rows; i++) {
		printf("%d行%d列%d \n",L->data[i].row,L->data[i].col,L->data[i].value);
	}
}
 
//遍历输出稀疏矩阵  矩阵形式
void bianli2(Arrays *L) {
	int flag = 1;         //flag代表 
	for (int i = 1; i <= L->rows; i++) {
		for (int j = 1; j <=L->cols; j++) {
			if (L->data[flag].value!=0&&L->data[flag].row==i&&L->data[flag].col==j) {
				printf(" %d", L->data[flag].value);
				flag++;
			}
			else {
				printf(" 0");
			}
		}
		printf("\n");
	}
}
//矩阵普通转置(按列)
int Transform(Arrays a,Arrays *b){   // //a为原矩阵，b为转置后的矩阵
	b->cols=a.cols;
	b->nums=a.nums;
	b->rows=a.rows;
	if(b->nums>0){
		int j=1;
		for(int k=1;k<=a.cols;k++){
			for(int i=1;i<=a.nums;i++){    //进入非零元素循环 
				if(a.data[i].col==k){      //如果在每一个列中有非零元素，则进行转置操作 
					b->data[j].row=a.data[i].col;    //j代表表B的非零元素个数值，它从1开始。 
					b->data[j].col=a.data[i].row;
					b->data[j].value=a.data[i].value;
					j++;
					if(j>a.nums) return false;
				}
			} 
		}
	}
} 
//矩阵快速转置
void FastTransform(Arrays *a,Arrays *b){   //a为原矩阵，b为转置后的矩阵 
	int num[max],position[max];
	int col,i,k,m;
	b->cols=a->cols;
	b->nums=a->nums;
	b->rows=a->rows;
	if(b->nums>0){
		for(col=1;col<=a->cols;col++){   //首先将num数组的数值都赋值为0 
			num[col]=0;
		}
		for(i=1;i<=a->nums;i++){   //再遍历非零元素，把非零元素的列所在的num数组进行++操作 
			num[a->data[i].col]++;
		} 
		position[1]=1;     //第一个非零元素的position值定义为1 
	 	for(col=2;col<=a->cols;col++){
		position[col]=position[col-1]+num[col-1];   //前一列非零元素的起始位置加非零元素的个数等于后一列的起始位置 
		}
		for(k=1;k<=a->nums;k++){   //对非零元素进行遍历并依次转置 
			col=a->data[k].col; 
			m=position[col];
			b->data[m].row=a->data[k].col;
			b->data[m].col=a->data[k].row;
			b->data[m].value=a->data[k].value;
			position[col]++;
		} 
	}
} 
//矩阵加法
int ADD(Arrays a,Arrays b,Arrays *c){
	int k=1,i,j;      //i为a的元素数目，j为b的元素数目，k为c的元素数目 
	
	//同行同列的才能相加 
	if(a.cols!=b.cols||a.rows!=b.rows){
		return false;
	}
	
	c->cols=a.cols;   //赋值总行数，总列数 
	c->rows=a.rows;
	//进行遍历赋值 
	for(i=1,j=1;i<=a.nums&&j<=b.nums;){
	   
	   //B的行号大于A直接将A中元素加入C矩阵 
		if(a.data[i].row<b.data[j].row){
			c->data[k].col=a.data[i].col;
			c->data[k].row=a.data[i].row;
			c->data[k].value=a.data[i].value;
			k++;       //C元素向后增一位 
			i++;       //a赋值则a元素向后增一位，如果时b则b元素向后增一位 
		}
		//B的行号小于A直接将B中元素加入C矩阵
		else if(a.data[i].row>b.data[j].row){
			c->data[k].col=b.data[j].col;
			c->data[k].row=b.data[j].row;
			c->data[k].value=b.data[j].value;
			k++;
			j++; 
		}else{  //行号相同 
			
			//B的列号小于A直接将B中元素加入C矩阵
			if(a.data[i].col>b.data[j].col) {
			c->data[k].col=b.data[j].col;
			c->data[k].row=b.data[j].row;
			c->data[k].value=b.data[j].value;
			k++;
			j++;
			}
			
			//B的列号大于A直接将A中元素加入C矩
			else if(a.data[i].col<b.data[j].col){
			c->data[k].col=a.data[i].col;
			c->data[k].row=a.data[i].row;
			c->data[k].value=a.data[i].value;
			k++;
			i++;
			}
			//相等 
			else {
				 
				c->data[k].col=a.data[i].col;
				c->data[k].row=a.data[i].row;
				c->data[k].value=a.data[i].value+b.data[j].value;
				k++;
				i++;
				j++;
			}
		}
	}
	while(i<=a.nums){ //B取完A未取完
	
			//将A中所剩元素依次加入到C中
		c->data[k].col=a.data[i].col;
		c->data[k].row=a.data[i].row;
		c->data[k].value=a.data[i].value;
		k++;
		i++;
	}   
	while(j<=b.nums){  //A取完B未取完
			
			//将A中所剩元素依次加入到C中
		c->data[k].col=b.data[j].col;
		c->data[k].row=b.data[j].row;
		c->data[k].value=b.data[j].value;
		k++;
		j++;
	}
}
    
			
 
 
//矩阵减法
int reduce(Arrays a,Arrays b,Arrays *c){   //调用加法操作，在b矩阵基础上乘 -1 在加 a矩阵 
	for(int i=1;i<=b.nums;i++){
		b.data[i].value=b.data[i].value*-1;
	}
	ADD(a,b,c);
} 
//矩阵乘法
int multipe(Arrays a,Arrays b,Arrays *c){
	int m=1,n=1,k=1;      //m为a的元素数目，n为b的元素数目，k为c的元素数目 
	if(a.cols!=b.cols||a.rows!=b.rows){
		return false;
	}
	c->cols=a.cols;
	c->rows=a.rows;
	while(m<=a.nums&&n<=b.nums){
		if(a.data[m].col==b.data[n].col&&a.data[m].row==b.data[n].row){
			c->data[k].col=a.data[m].col;
			c->data[k].row=a.data[m].row;
			c->data[k].value=a.data[m].value*b.data[n].value;
		}
		m++;n++;k++;
	}
} 
int main(){
	Arrays s;
	Arrays s1;
	Arrays s2;
	Arrays s3;
	int row, col, num;
	//创建
	printf("请依次输入稀疏矩阵A的行数,列数,非零元个数(用空格隔开):\n");
	scanf("%d %d %d", &row, &col, &num);
	InitArray(&s,row,col,num);
	bianli2(&s);
	printf("请依次输入稀疏矩阵B的行数,列数,非零元个数(用空格隔开):\n");
	scanf("%d %d %d", &row, &col, &num);
	InitArray(&s1,row,col,num);
	bianli2(&s1);
	printf("---------矩阵B的转置为：\n");
	Transform(s1,&s3);
	bianli2(&s3);
	printf("---------矩阵相乘为：\n"); 
	multipe(s,s1,&s2);
	bianli2(&s2);
	printf("---------矩阵相加为：\n"); 
	ADD(s,s1,&s2);
	bianli2(&s2);
	printf("---------矩阵相减为：\n");
	reduce(s,s1,&s2); 
	bianli2(&s2);
}